from sortedcontainers import SortedList
import numpy as np
import json
import random
from pathlib import Path
from datetime import datetime
from UAS.algorithm.chromosome import Chromosome

class LocalSearch:
    def __init__(self, valid_points, valid_matrix, node_mapping, profits,
                time_limit, valid_time, penalty_rate, penalty_interval):
        """
        初始化local search
        :param valid_points: 有效点位列表
        :param valid_matrix: 有效邻接矩阵
        :param node_mapping: 节点编码映射
        :param profits: 点位收益列表
        :param time_limit: 限定时间
        :param valid_time: 有效时间
        :param penalty_rate: 惩罚值
        :param penalty_interval: 惩罚间隔
        """
        self.valid_points = valid_points
        self.valid_matrix = valid_matrix
        self.node_mapping = node_mapping
        self.profits = profits
        self.reverse_mapping = {v: k for k, v in node_mapping.items()}
        self.time_limit = time_limit
        self.valid_time = valid_time
        self.penalty_rate = penalty_rate
        self.penalty_interval = penalty_interval
        # 初始化操作计数器
        self.operation_counts = {
            'shift_success': 0,
            'swap_success': 0,
            'destruct_success': 0
        }

    def LS(self, chromosome):
        """实现局部搜索算子"""
        improved = True
        no_improve_count = 0
        max_no_improve = 3  # 最大无改进次数
        while improved or no_improve_count < max_no_improve:
            if not improved:
                no_improve_count += 1
                #print(f"无改进次数: {no_improve_count}/{max_no_improve}")
            else:
                no_improve_count = 0  # 重置计数器
            improved = False
            
            # 创建操作列表并随机排序
            operations = ['shift', 'swap', 'destruct']
            random.shuffle(operations)
                        
            #print(f"\n当前优化顺序: {operations}")
            
            for op in operations:
                if op == 'shift':
                    # Shift操作
                    #print("执行Shift操作...")
                    best_gain = 0
                    best_seq = chromosome.sequence.copy()
                    one_pos = chromosome.sequence.index(1)  # 获取元素1的位置
                    for i in range(1, len(chromosome.sequence)-1):
                        for j in range(1, len(chromosome.sequence)):
                            if i == j: continue
                            if j > one_pos: continue  # 如果插入位置在1之后则跳过
                            #print(f"i={i}, j={j}")
                            #print(f"chromosome.sequence = {chromosome.sequence}")
                            new_seq = chromosome.sequence[:i] + chromosome.sequence[i+1:]
                            new_seq.insert(j, chromosome.sequence[i])
                            #print(f"new_seq = {new_seq}")
                            temp_chr = Chromosome(new_seq, self.valid_points, self.profits, self.valid_matrix,
                                                self.time_limit, self.valid_time,
                                                self.penalty_interval, self.penalty_rate)
                            if temp_chr.total_profit > best_gain:
                                best_gain = temp_chr.total_profit
                                best_seq = new_seq
                    if best_gain > chromosome.total_profit:
                        #print(f"Shift优化成功，收益提升: {best_gain - chromosome.total_profit}")
                        self.operation_counts['shift_success'] += 1
                        chromosome = Chromosome(best_seq, self.valid_points, self.profits, self.valid_matrix,
                                              self.time_limit, self.valid_time,
                                              self.penalty_interval, self.penalty_rate)
                        improved = True
                        continue

                elif op == 'swap':
                    # Swap操作
                    #print("执行Swap操作...")
                    best_gain = 0
                    best_seq = chromosome.sequence.copy()
                    one_pos = chromosome.sequence.index(1)  # 获取元素1的位置
                    for i in range(1, len(chromosome.sequence)-1):
                        for j in range(i+1, len(chromosome.sequence)-1):
                            if i > one_pos and j > one_pos:  # 如果i和j都在1之后则跳过
                                continue
                            new_seq = chromosome.sequence.copy()
                            new_seq[i], new_seq[j] = new_seq[j], new_seq[i]
                            temp_chr = Chromosome(new_seq, self.valid_points, self.profits, self.valid_matrix,
                                                self.time_limit, self.valid_time,
                                                self.penalty_interval, self.penalty_rate)
                            if temp_chr.total_profit > best_gain:
                                best_gain = temp_chr.total_profit
                                best_seq = new_seq
                    if best_gain > chromosome.total_profit:
                        # print(f"Swap优化成功，收益提升: {best_gain - chromosome.total_profit}")
                        self.operation_counts['swap_success'] += 1
                        chromosome = Chromosome(best_seq, self.valid_points, self.profits, self.valid_matrix,
                                              self.time_limit, self.valid_time,
                                              self.penalty_interval, self.penalty_rate)
                        improved = True
                        continue

                elif op == 'destruct':
                    # Destruct and Repair操作
                    #print("执行Destruct and Repair操作...")
                    points_between_0_1 = self._get_points_between_0_1(chromosome.sequence)
                    
                    if len(points_between_0_1) == 0:
                        continue  # 无可用点则跳过
                    elif len(points_between_0_1) <= 2:
                        delete_count = 1
                    else:
                        delete_count = random.randint(1, min(3, len(points_between_0_1)))
                    
                    # 随机选择要移除的点（破坏阶段）
                    removed = random.sample(points_between_0_1, delete_count)
                    
                    # 生成破坏后的序列（移除选中的点）
                    destroyed_seq = [p for p in chromosome.sequence if p not in removed]
                    
                    # 使用BIA算法重新插入被移除的点（修复阶段）
                    # 1. 将0和1之间的剩余点作为基础序列
                    base_sequence = destroyed_seq+removed
                
                    # 3. 使用BIA算法插入到0和1之间（优先级为0到1之间的位置）
                    # 调用_BIA方法，传入当前基础序列和alpha参数（论文中的插入成本权重）
                    repaired_chr = self._BIA(
                        current_sol=Chromosome(base_sequence, self.valid_points, self.profits, self.valid_matrix,
                                            self.time_limit, self.valid_time, self.penalty_interval, self.penalty_rate),
                        alpha=1.0  # 根据论文，alpha=1.0表示直接使用时间成本插入
                    )
                    
                    # 4. 确保插入后的序列包含0和1，并且被移除点插入到0和1之间
                    optimized_seq = repaired_chr.sequence
                     # 比较优化后结果
                    temp_chr = Chromosome(
                        optimized_seq, 
                        self.valid_points, 
                        self.profits, 
                        self.valid_matrix,
                        self.time_limit, 
                        self.valid_time,
                        self.penalty_interval, 
                        self.penalty_rate
                    )
                    
                    # 比较优化后结果并验证时间成本
                    if (temp_chr.total_profit > chromosome.total_profit and
                        temp_chr.total_cost <= self.valid_time):
                        # print(f"Destruct优化成功，收益提升: {temp_chr.total_profit - chromosome.total_profit}")
                        self.operation_counts['destruct_success'] += 1
                        chromosome = temp_chr
                        improved = True
                        continue

                #print(f"当前最优解: 收益={chromosome.total_profit}, 成本={chromosome.total_cost}")
                #print("-" * 50)

        # 输出优化成功统计
        # print("\n优化成功统计:")
        # print(f"Shift优化成功: {self.operation_counts['shift_success']}次")
        # print(f"Swap优化成功: {self.operation_counts['swap_success']}次") 
        # print(f"Destruct优化成功: {self.operation_counts['destruct_success']}次")
        # print("-" * 50)

        return chromosome

    def IDCH(self, current_sol=None, max_iterations=100, slow_version=False, is_diversification=False):
        """按照论文3.3节改进的IDCH算法"""
        # 初始化阶段
        if current_sol is None:
            current_sol = self._BIA()
        else:
            current_sol = Chromosome(
                current_sol.sequence.copy(),
                self.valid_points,
                self.profits,
                self.valid_matrix,
                self.time_limit,
                self.valid_time,
                self.penalty_interval,
                self.penalty_rate
            )

        best_sol = current_sol
        no_improve = 0
        n = len(self.valid_points)
        m = 1  # 假设车辆数m=1

       # 优先级字典初始化（论文式累计惩罚机制）
        priorities = {point: 0 for point in self.valid_points}
        destruction_size = max(3, n//m) if is_diversification else 3
        max_iterations = 50 if is_diversification else max_iterations
        
        # 多样化处理参数调整
        iter_since_improve = 0
        for iter in range(max_iterations):
            #print(f"\n迭代 {iter + 1}/{max_iterations}")
            
            # --- 破坏阶段 ---
            removable = [p for p in current_sol.sequence if p not in [0, 1]]
            k = min(destruction_size, len(removable))
            removed = random.sample(removable, k=k) if removable else []
            destroyed_seq = [p for p in current_sol.sequence if p not in removed]
            
            # 应用2-opt优化
            optimized_seq = self._2opt(destroyed_seq)
            current_sol = Chromosome(optimized_seq, self.valid_points, self.profits, self.valid_matrix,
                                self.time_limit, self.valid_time,
                                self.penalty_interval, self.penalty_rate)
            # --- 重建阶段（带优先级的并行插入）---
            all_uninserted = list(set(removed + [p for p in self.valid_points 
                                            if p not in current_sol.sequence]))
            uninserted = sorted(all_uninserted, 
                            key=lambda x: (-priorities.get(x, 0), 
                                          current_sol.sequence.index(x) if x in current_sol.sequence else len(current_sol.sequence)))
            
            rebuilt_sol = self._PBIA(current_sol, uninserted, priorities)
            
            # --- 更新阶段 ---
            if rebuilt_sol.total_profit > best_sol.total_profit:
                best_sol = rebuilt_sol
                no_improve = 0
                iter_since_improve = 0
            else:
                no_improve += 1
                iter_since_improve += 1
                # 累计惩罚未插入的点位
                for point in uninserted:
                    priorities[point] += self.profits[self.valid_points.index(point)]
            
            # 多样化处理
            if iter_since_improve >= n//2 and is_diversification:
                # 大规模破坏并重新优化
                removable = [p for p in best_sol.sequence if p not in [0, 1]]
                k_diverse = min(len(removable), n//m)
                removed_diverse = random.sample(removable, k=k_diverse)
                diverse_seq = [p for p in best_sol.sequence if p not in removed_diverse]
                optimized_diverse = self._2opt(diverse_seq)
                optimized_chr = Chromosome(optimized_diverse, self.valid_points, self.profits, self.valid_matrix,
                                         self.time_limit, self.valid_time,
                                         self.penalty_interval, self.penalty_rate)
                best_sol = self._PBIA(optimized_chr, removed_diverse, priorities)
                iter_since_improve = 0

            # 慢速版本处理
            if slow_version and not is_diversification and no_improve >= n**2:
                return self._apply_deep_diversification(best_sol, priorities, n, m)

        # 最终插入剩余点（所有阶段）
        best_sol = self._insert_remaining_points(best_sol, priorities)
        return best_sol

    def _PBIA(self, base_sol, uninserted, priorities, alpha=1.0):
        """Prioritized Best Insertion Algorithm with profit-based delta"""
        # Initialize chromosome like _BIA
        if base_sol is None:
            chromosome = Chromosome([0, 1], self.valid_points, self.profits, self.valid_matrix,
                                  self.time_limit, self.valid_time,
                                  self.penalty_interval, self.penalty_rate)
        else:
            chromosome = Chromosome(base_sol.sequence.copy(), self.valid_points, self.profits, self.valid_matrix,
                                  self.time_limit, self.valid_time,
                                  self.penalty_interval, self.penalty_rate)
        
        # Get 0 and 1 positions
        zero_idx = chromosome.sequence.index(0)
        one_idx = chromosome.sequence.index(1)
        base_sequence = chromosome.sequence[zero_idx:one_idx+1]
        
        # Get uninserted points like _BIA
        candidate_points = [p for p in uninserted if p not in chromosome.sequence] + \
                          [p for p in chromosome.sequence if chromosome.sequence.index(p) > one_idx]
        
        # Sort candidate points by priority
        candidate_points = sorted(candidate_points,
                                key=lambda x: (-priorities.get(x, 0),
                                              chromosome.sequence.index(x) if x in chromosome.sequence else len(chromosome.sequence)))
        
        # Insert points using best insertion algorithm
        no_insertion_count = 0
        current_index = 0
        while candidate_points:
            prev_length = len(candidate_points)
            point = candidate_points[current_index]
            
            best_delta = float('inf')
            best_pos = -1
            
            # Only evaluate positions strictly between 0 and 1
            if zero_idx < one_idx:
                for i in range(zero_idx, one_idx):
                    a = base_sequence[i]
                    b = base_sequence[i+1]
                    
                    # Calculate insertion cost with alpha parameter
                    point_profit = self.profits[self.valid_points.index(point)]
                    delta = (self.valid_matrix[a][point] + 
                            self.valid_matrix[point][b] - 
                            self.valid_matrix[a][b]) / (point_profit ** alpha)
                    
                    # Create temporary chromosome to validate feasibility
                    temp_seq = base_sequence[:i+1] + [point] + base_sequence[i+1:]
                    temp_chr = Chromosome(temp_seq, self.valid_points, self.profits, self.valid_matrix,
                                        self.time_limit, self.valid_time,
                                        self.penalty_interval, self.penalty_rate)
                    
                    # Select best insertion position
                    if delta < best_delta and temp_chr.total_cost <= self.time_limit:
                        best_delta = delta
                        best_pos = i+1

                # Perform insertion if valid position found
                if best_pos != -1 and zero_idx < best_pos <= one_idx:
                    base_sequence.insert(best_pos, point)
                    candidate_points.remove(point)
                    # Update 0 and 1 positions
                    zero_idx = base_sequence.index(0)
                    one_idx = base_sequence.index(1)
                    current_index = min(current_index, len(candidate_points) - 1)
                else:
                    current_index = (current_index + 1) % len(candidate_points)

            # Check if no points were inserted this iteration
            if len(candidate_points) == prev_length:
                no_insertion_count += 1
                if no_insertion_count >= 2:
                    break
            else:
                no_insertion_count = 0
        
        # Append remaining uninserted points to sequence like _BIA
        new_sequence = base_sequence + candidate_points
        if len(new_sequence) != len(self.valid_points):
            raise ValueError(f"Sequence length {len(new_sequence)} does not match valid_points length {len(self.valid_points)}")
        
        chromosome.sequence = new_sequence
        return chromosome

    def _apply_deep_diversification(self, best_sol, priorities, n, m):
        """Apply deep diversification by removing and reinserting points"""
        # Create working copy of chromosome
        working_chr = Chromosome(best_sol.sequence.copy(), self.valid_points, self.profits, self.valid_matrix,
                               self.time_limit, self.valid_time,
                               self.penalty_interval, self.penalty_rate)
        
        # Remove points for diversification
        removable = [p for p in working_chr.sequence if p not in [0, 1]]
        k_diverse = min(len(removable), max(1, n//m))
        removed_diverse = random.sample(removable, k=k_diverse)
        diverse_seq = [p for p in working_chr.sequence if p not in removed_diverse]
        
        # Optimize sequence with 2-opt
        optimized_diverse = self._2opt(diverse_seq)
        
        # Create new chromosome from optimized sequence
        optimized_chr = Chromosome(optimized_diverse, self.valid_points, self.profits, self.valid_matrix,
                                 self.time_limit, self.valid_time,
                                 self.penalty_interval, self.penalty_rate)
        
        # Reinsert removed points using PBIA
        return self._PBIA(optimized_chr, removed_diverse, priorities)

    def _insert_remaining_points(self, chromosome, priorities):
        """优化插入剩余点，寻找最佳插入位置"""
        # Create working copy of chromosome
        working_chr = Chromosome(chromosome.sequence.copy(), self.valid_points, self.profits, self.valid_matrix,
                               self.time_limit, self.valid_time,
                               self.penalty_interval, self.penalty_rate)
        
        # Get remaining points sorted by priority
        remaining = [p for p in self.valid_points if p not in working_chr.sequence]
        sorted_remaining = sorted(remaining, key=lambda x: -priorities.get(x, 0))
        
        # Insert remaining points using best insertion
        for point in sorted_remaining:
            best_cost = float('inf')
            best_pos = -1
            
            # Find best insertion position
            for i in range(len(working_chr.sequence)-1):
                a, b = working_chr.sequence[i], working_chr.sequence[i+1]
                delta_time = (self.valid_matrix[a][point] 
                            + self.valid_matrix[point][b] 
                            - self.valid_matrix[a][b])
                
                # Validate insertion with temporary chromosome
                temp_seq = working_chr.sequence[:i+1] + [point] + working_chr.sequence[i+1:]
                temp_chr = Chromosome(temp_seq, self.valid_points, self.profits, self.valid_matrix,
                                    self.time_limit, self.valid_time,
                                    self.penalty_interval, self.penalty_rate)
                
                # Select best position
                if delta_time < best_cost and temp_chr.total_cost <= self.time_limit:
                    best_cost = delta_time
                    best_pos = i+1
            
            # Insert point if valid position found
            if best_pos != -1:
                working_chr.sequence.insert(best_pos, point)
        
        return working_chr

    def _get_points_between_0_1(self, sequence):
        """获取0到1之间的点"""
        try:
            start = sequence.index(0)
            end = sequence.index(1)
            if start < end:
                return sequence[start+1:end]
            return []
        except ValueError:
            return []

    def _random_alpha(self):
        r1, r2 = random.random(), random.random()
        return 1 + 2 * (r1 / (r1 + r2)) if (r1 + r2) != 0 else 1.5
    

    def _BIA(self, current_sol=None, alpha=1.0):
        """Best Insertion Algorithm with profit-based delta"""
        # Initialize chromosome
        if current_sol is None:
            chromosome = Chromosome([0, 1], self.valid_points, self.profits, self.valid_matrix,
                                  self.time_limit, self.valid_time,
                                  self.penalty_interval, self.penalty_rate)
        else:
            chromosome = Chromosome(current_sol.sequence.copy(), self.valid_points, self.profits, self.valid_matrix,
                                  self.time_limit, self.valid_time,
                                  self.penalty_interval, self.penalty_rate)
        # Get uninserted points
        # 获取0,1的位置
        zero_idx = chromosome.sequence.index(0)
        one_idx = chromosome.sequence.index(1)
        base_sequence = chromosome.sequence[zero_idx:one_idx+1]
        # 未插入的点包括：
        # 1. 不在当前序列中的有效点
        # 2. 当前序列中1之后的点
        uninserted = [p for p in self.valid_points if p not in chromosome.sequence] + \
                    [p for p in chromosome.sequence if chromosome.sequence.index(p) > one_idx]
        
        # Insert points using best insertion
        no_insertion_count = 0
        current_index = 0  # Track current position in uninserted list
        while uninserted:
            prev_length = len(uninserted)
            
            # Get current point to insert
            point = uninserted[current_index]
                       
            # Ensure 0 comes before 1
            if zero_idx > one_idx:
                continue
                
            # Only evaluate positions strictly between 0 and 1
            if zero_idx >= one_idx:
                continue  # 0必须在1之前
                    
            best_delta = float('inf')
            best_point = None
            best_pos = -1
            # 确保插入位置在0和1之间
            for i in range(zero_idx, one_idx):
                # Get adjacent points
                a = base_sequence[i]
                b = base_sequence[i+1]
                
                # Calculate insertion cost
                point_profit = self.profits[self.valid_points.index(point)]
                delta = (self.valid_matrix[a][point] + 
                        self.valid_matrix[point][b] - 
                        self.valid_matrix[a][b]) / (point_profit ** alpha)
                
                # Create temporary chromosome using base_sequence
                temp_seq = base_sequence[:i+1] + [point] + base_sequence[i+1:]
                temp_chr = Chromosome(temp_seq, self.valid_points, self.profits, self.valid_matrix,
                                self.time_limit, self.valid_time,
                                self.penalty_interval, self.penalty_rate)
                # Select best insertion based on profit and delta
                if (temp_chr.total_profit > chromosome.total_profit and
                    (best_point is None or delta < best_delta)):
                    best_point = point
                    best_pos = i+1
                    best_delta = delta
        
            # Insert best point if found and position is strictly between 0 and 1
            if best_point is not None and zero_idx < best_pos <= one_idx:
                # Create temporary sequence to validate insertion
                temp_seq = base_sequence[:best_pos] + [best_point] + base_sequence[best_pos:]
                #print(f"================inserting point: {best_point}, best_pos: {best_pos}, temp_seq: {temp_seq}")
                
                # 验证插入后的序列是否仍然包含0和1
                if 0 not in temp_seq or 1 not in temp_seq:
                    continue
                temp_chr = Chromosome(temp_seq, self.valid_points, self.profits, self.valid_matrix,
                                self.time_limit, self.valid_time,
                                self.penalty_interval, self.penalty_rate)
                    
                # Only insert if the new sequence is valid
                if temp_chr.total_cost <= self.valid_time:
                    base_sequence.insert(best_pos, best_point)
                    uninserted.remove(best_point)
                    # 获取0,1的位置
                    zero_idx = base_sequence.index(0)
                    one_idx = base_sequence.index(1)
                    # Move to next point in uninserted list
                    current_index = min(current_index, len(uninserted) - 1)
            else:
                # Move to next point if current one cannot be inserted
                current_index = (current_index + 1) % len(uninserted)

            # Check if no points were inserted this iteration
            if len(uninserted) == prev_length:
                no_insertion_count += 1
                if no_insertion_count >= 2:
                    break
            else:
                no_insertion_count = 0
        
        # Append remaining uninserted points to sequence
        new_sequence = base_sequence + uninserted
        # Verify length matches valid_points
        if len(new_sequence) != len(self.valid_points):
            raise ValueError(f"Sequence length {len(new_sequence)} does not match valid_points length {len(self.valid_points)}")
        # Update chromosome sequence
        chromosome.sequence = new_sequence
        return chromosome

    def _2opt(self, sequence):
        improved = True
        best_seq = sequence.copy()
        max_attempts = 200
        attempts = 0

       # 获取0和1的位置
        zero_idx = best_seq.index(0)
        one_idx = best_seq.index(1)
        
        # 确保0在1之前
        if zero_idx > one_idx:
            return best_seq
            
        # 只交换0和1之间的点
        start = zero_idx + 1
        end = one_idx - 1
        
        #print(f"self.valid_matrix = {self.valid_matrix}")
        while improved and attempts < max_attempts:
            improved = False
            for i in range(start, end):
                for j in range(i+1, end+1):
                    if j-i == 1: continue
                    # 计算原始成本
                    a, b = best_seq[i-1], best_seq[i]
                    c, d = best_seq[j], best_seq[j+1]
                    original_cost = (self.valid_matrix[a][b] +
                                   self.valid_matrix[c][d])
                    
                    # 计算新成本
                    new_cost = (self.valid_matrix[a][c] +
                              self.valid_matrix[b][d])
                    
                    # 检查是否改进
                    if new_cost < original_cost:
                        # 创建新序列
                        new_seq = best_seq[:i] + best_seq[i:j+1][::-1] + best_seq[j+1:]
                        
                        # 创建新染色体并验证时间约束
                        new_chr = Chromosome(new_seq, self.valid_points, self.profits, self.valid_matrix,
                                           self.time_limit, self.valid_time,
                                           self.penalty_interval, self.penalty_rate)
                        if new_chr.total_cost <= self.time_limit:
                            #print(f"new_chr.total_cost = {new_chr.total_cost}")
                            #print(f"time_limit = {self.time_limit}")
                            #print(f"new_seq = {new_seq}")
                            best_seq = new_seq
                            improved = True
                            attempts += 1
                            break
                if improved:
                    break
        return best_seq

if __name__ == "__main__":
    import sys
    from pathlib import Path
    # 添加项目根目录到Python路径
    sys.path.append(str(Path(__file__).parent.parent.parent))
    from UAS.data.graph_builder import GraphBuilder
    from UAS.data.excel_parser import ExcelParser
    
    # 初始化解析器和图构建器
    parser = ExcelParser("d:/Work/Projects/UAS/valid_points.xlsx", 
                        "d:/Work/Projects/UAS/valid_matrix.xlsx")
    parser.load_data()
    builder = GraphBuilder(parser)
    
    # 获取graph_builder的数据
    valid_points, profits, valid_matrix, node_mapping = builder.build_graph()
    
    # 初始化LocalSearch
    time_limit = 120
    valid_time = 150
    penalty_rate = 1
    penalty_interval = 10
    local_search = LocalSearch(valid_points, valid_matrix, node_mapping, profits,
                             time_limit, valid_time, penalty_rate, penalty_interval)

    # 定义多个固定测试序列
    test_sequences = [
        # [0, 27, 7, 21, 10, 9, 6, 26, 31, 15, 8, 5, 29, 13, 1, 25, 19, 11, 18, 2, 20, 3, 28, 30, 23, 4, 12, 22, 17, 24, 14, 16],
        # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31],
        # [0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1],
        # [0, 16, 1, 17, 2, 18, 3, 19, 4, 20, 5, 21, 6, 22, 7, 23, 8, 24, 9, 25, 10, 26, 11, 27, 12, 28, 13, 29, 14, 30, 15, 31],
        # [0, 4, 24, 10, 13, 30, 29, 14, 5, 17, 11, 23, 25, 3, 12, 16, 9, 31, 19, 1, 7, 20, 22, 6, 2, 27, 28, 8, 15, 18, 26, 21],
        # [0, 4, 24, 10, 13, 29, 17, 11, 12, 25, 16, 9, 23, 31, 30, 14, 5, 3, 19, 1, 7, 20, 22, 6, 18, 8, 2, 15, 27, 28, 26, 21],
        # [0, 27, 7, 21, 10, 9, 29, 13, 1, 6, 26, 31, 15, 8, 5, 25, 19, 11, 18, 2, 20, 3, 28, 30, 23, 4, 12, 22, 17, 24, 14, 16],
        # [0, 9, 30, 27, 7, 21, 25, 24, 1, 10, 29, 13, 6, 26, 31, 15, 8, 5, 19, 11, 18, 2, 20, 3, 28, 23, 4, 12, 22, 17, 14, 16],
        # [0, 19, 23, 6, 1, 10, 8, 11, 7, 20, 3, 30, 31, 18, 9, 26, 29, 16, 24, 15, 4, 25, 14, 27, 2, 28, 17, 5, 13, 21, 22, 12],
        # [0, 28, 1, 12, 20, 10, 5, 26, 9, 6, 27, 11, 24, 25, 17, 22, 30, 23, 15, 4, 2, 3, 21, 31, 19, 13, 29, 8, 7, 18, 16, 14],
        # [0, 23, 16, 17, 27, 13, 4, 2, 1, 31, 22, 24, 26, 28, 6, 18, 10, 11, 19, 9, 15, 25, 12, 7, 20, 29, 8, 21, 3, 30, 5, 14],
        # [0, 11, 12, 17, 27, 13, 4, 25, 1, 24, 10, 3, 30, 29, 16, 28, 14, 9, 19, 7, 20, 22, 6, 2, 18, 15, 23, 21, 5, 26, 31, 8],
        # [0, 15, 9, 19, 13, 5, 21, 26, 22, 25, 16, 1, 20, 23, 29, 6, 24, 18, 11, 30, 28, 10, 3, 12, 4, 2, 7, 8, 14, 27, 17, 31],
        # [0, 12, 23, 11, 24, 1, 10, 8, 27, 19, 16, 25, 9, 29, 2, 3, 28, 4, 15, 14, 17, 6, 30, 13, 18, 22, 7, 26, 21, 20, 5, 31],
        # [0, 31, 12, 1, 15, 19, 27, 6, 8, 21, 29, 24, 9, 4, 18, 16, 5, 10, 20, 14, 22, 2, 11, 23, 17, 26, 7, 25, 30, 13, 3, 28],
        # [0, 11, 13, 2, 22, 30, 9, 19, 1, 3, 28, 31, 23, 21, 6, 29, 8, 18, 7, 4, 24, 17, 20, 10, 27, 12, 25, 14, 5, 15, 26, 16],
        [0, 6, 4, 1, 23, 30, 17, 2, 8, 9, 25, 13, 20, 29, 3, 26, 19, 5, 14, 27, 7, 31, 24, 18, 22, 11, 12, 15, 10, 28, 21, 16],
        [0, 16, 5, 6, 21, 9, 3, 1, 4, 28, 2, 23, 12, 26, 8, 27, 10, 14, 30, 15, 31, 22, 13, 18, 29, 20, 24, 25, 17, 19, 11, 7],
        [0, 29, 28, 30, 23, 1, 26, 31, 17, 24, 27, 22, 25, 14, 8, 15, 2, 5, 12, 13, 6, 10, 18, 21, 19, 3, 16, 4, 20, 7, 11, 9],
        [0, 25, 21, 3, 13, 29, 1, 20, 22, 28, 10, 31, 9, 15, 11, 24, 7, 6, 2, 27, 8, 30, 16, 17, 19, 23, 18, 12, 5, 26, 4, 14],
        [0, 12, 5, 1, 9, 10, 6, 30, 27, 20, 2, 4, 15, 31, 17, 18, 26, 3, 19, 14, 24, 25, 28, 23, 21, 22, 16, 29, 7, 8, 13, 11],
        [0, 11, 1, 6, 27, 26, 24, 29, 4, 20, 12, 7, 28, 3, 15, 22, 10, 18, 30, 19, 13, 9, 16, 25, 21, 23, 5, 8, 2, 14, 17, 31]
        # [0, 19, 23, 29, 26, 27, 11, 24, 13, 4, 1, 31, 12, 9, 10, 5, 8, 28, 20, 30, 3, 17, 16, 14, 18, 2, 25, 7, 6, 15, 21, 22]
    ]

    # 初始化统计信息
    total_stats = {
        'shift_success': 0,
        'swap_success': 0,
        'destruct_success': 0,
        'total_improvement': 0.0,
        'best_solution': None,
        'best_improvement': 0.0
    }

    # 对每个测试序列进行优化
    for i, test_sequence in enumerate(test_sequences):
        print(f"\n=== 测试序列 {i+1}/{len(test_sequences)} ===")
        initial_solution = Chromosome(test_sequence, valid_points, profits, valid_matrix,
                                    time_limit, valid_time, penalty_interval, penalty_rate)
        
        print("\n初始解：")
        print(f"序列: {initial_solution.sequence}")
        print(f"收益: {initial_solution.total_profit}")
        print(f"成本: {initial_solution.total_cost}")
        print(f"是否有效: {'是' if initial_solution.total_cost <= valid_time else '否'}")

        # 重置操作计数器
        local_search.operation_counts = {
            'shift_success': 0,
            'swap_success': 0,
            'destruct_success': 0
        }

        # 执行局部搜索优化
        print("\n开始局部搜索优化：")
        optimized_solution = local_search.LS(initial_solution)
        
        # 计算改进程度
        improvement = optimized_solution.total_profit - initial_solution.total_profit
        
        # 更新统计信息
        total_stats['shift_success'] += local_search.operation_counts['shift_success']
        total_stats['swap_success'] += local_search.operation_counts['swap_success']
        total_stats['destruct_success'] += local_search.operation_counts['destruct_success']
        total_stats['total_improvement'] += improvement
        
        if improvement > total_stats['best_improvement']:
            total_stats['best_improvement'] = improvement
            total_stats['best_solution'] = optimized_solution

        print("\n优化结果：")
        print(f"优化后序列: {optimized_solution.sequence}")
        print(f"优化后收益: {optimized_solution.total_profit} (改进: {improvement})")
        print(f"优化后成本: {optimized_solution.total_cost}")
        print(f"是否有效: {'是' if optimized_solution.total_cost <= valid_time else '否'}")

    # 输出总体统计信息
    print("\n=== 总体统计 ===")
    print(f"总Shift优化成功次数: {total_stats['shift_success']}")
    print(f"总Swap优化成功次数: {total_stats['swap_success']}")
    print(f"总Destruct优化成功次数: {total_stats['destruct_success']}")
    print(f"总收益改进: {total_stats['total_improvement']}")
    print(f"最大单次改进: {total_stats['best_improvement']}")
    print("\n最佳解：")
    print(f"序列: {total_stats['best_solution']}")
